package com.cjm.algorithm.leetcode;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

public class ThreeSumClosest16 {
    public static int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int ans = nums[0] + nums[1] + nums[2];
        for(int i=0;i<nums.length;i++) {
            int start = i+1, end = nums.length - 1;
            while(start < end) {
                int sum = nums[start] + nums[end] + nums[i];
                if(Math.abs(target - sum) < Math.abs(target - ans))
                    ans = sum;
                if(sum > target)
                    end--;
                else if(sum < target)
                    start++;
                else
                    return ans;
            }
        }
        return ans;
    }
    public static int threeSumClosest1(int[] nums, int target) {
        Arrays.sort(nums);
        int ans = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.length; i++) {
            int start = i+1,end = nums.length - 1;
            while (start<end) {
                int sum = nums[start] + nums[end] + nums[i];
                if (Math.abs(target - sum) <Math.abs(target - ans)) {
                    ans = sum;
                }
                if (sum > target){
                    end --;
                } else if (sum < target) {
                    start++;
                } else {
                    return ans;
                }
            }
        }
        return ans;
    }

    public static int threeSumClosest2(int[] nums, int target) {
        Arrays.sort(nums);
        int ans = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.length; i++) {
            int l = i + 1;
            int r = nums.length - 1;
            while (l<r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (Math.abs(target - ans) > Math.abs(target - sum)) {
                    ans = sum;
                }
                if (sum > target) {
                    r--;
                } else if (sum < target) {
                    l++;
                } else {
                    return sum;
                }
            }
        }
        return ans;
    }

    public static int threeSumClosest3(int[] nums, int target) {
        Arrays.sort(nums);
        int ans = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.length; i++) {
            int l = i + 1;
            int r = nums.length - 1;
            while (l<r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (Math.abs(target - sum) < Math.abs(target - ans)) {
                    ans = sum;
                }
                if (target > sum) {
                    l++;
                }else
                if (target < sum) {
                    r--;
                }else{return sum;}
            }
        }
        return ans;
    }
    public static void main(String[] args) {
        System.err.println(threeSumClosest(new int[]{-3, -2, -5, 3, -4}, -1));
    }
}
